package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归:4ms,47%, 2.7MB 100%
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return false
	}
	return check(root.Left, root.Right)
}
func check(p, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if q == nil || p == nil {
		return false
	}
	return q.Val == p.Val && check(q.Right, p.Left) && check(q.Left, p.Right)
}

//迭代4ms 47%， 2.9MB 5%
func isSymmetric1(root *TreeNode) bool {
	u, v := root, root
	q := []*TreeNode{}
	q = append(q, u)
	q = append(q, v)
	for len(q) > 0 {
		u, v = q[0], q[1]
		q = q[2:]
		if u == nil && v == nil {
			continue
		}
		if u == nil || v == nil {
			return false
		}
		if u.Val != v.Val {
			return false
		}
		q = append(q, u.Left)
		q = append(q, v.Right)

		q = append(q, u.Right)
		q = append(q, v.Left)
	}
	return true
}

func main() {
	fmt.Println(isSymmetric(&TreeNode{}))
	fmt.Println(isSymmetric1(&TreeNode{}))
}
